package primary.primary0;

public class S0053最大子数组和 {

    class Solution {

        /**
         * 100，直接递推完事了
         * 但是分治法要去猜他的特征
         * 假设两个位置为mn，那么m和n位置肯定是正数，并且m-1，n+1肯定是负数，并且从m往左，n往右加起来一定是负数
         * 分治法不会
         */
        public int maxSubArray(int[] nums) {
            if(nums == null || nums.length == 0){
                return -1;
            }
            int maxSum = nums[0];
            int preMaxSum = nums[0];
            for(int i = 1; i < nums.length; i++){
                preMaxSum = Math.max(preMaxSum + nums[i], nums[i]);
                maxSum = Math.max(preMaxSum, maxSum);
            }
            return maxSum;
        }
    }


    /**
     * 答案里的分治，注意分治要维护的内容，以及分支最小处理单元，这里必然是单个位置
     * 区间和，左起最大和，右起最大和，中间最大和
     */
    class Solution2 {
        public class Status {
            public int lSum, rSum, mSum, iSum;

            public Status(int lSum, int rSum, int mSum, int iSum) {
                this.lSum = lSum;
                this.rSum = rSum;
                this.mSum = mSum;
                this.iSum = iSum;
            }
        }

        public int maxSubArray(int[] nums) {
            return getInfo(nums, 0, nums.length - 1).mSum;
        }

        public Status getInfo(int[] a, int l, int r) {
            if (l == r) {
                return new Status(a[l], a[l], a[l], a[l]);
            }
            int m = (l + r) >> 1;
            Status lSub = getInfo(a, l, m);
            Status rSub = getInfo(a, m + 1, r);
            return pushUp(lSub, rSub);
        }

        public Status pushUp(Status l, Status r) {
            int iSum = l.iSum + r.iSum;
            int lSum = Math.max(l.lSum, l.iSum + r.lSum);
            int rSum = Math.max(r.rSum, r.iSum + l.rSum);
            int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
            return new Status(lSum, rSum, mSum, iSum);
        }
    }
}
